/**
 * 测试 STL Algorithm 堆相关算法
 *
 *      make_heap: O(N) 创建堆
 *      is_heap: O(N) 判断是否是堆
 *      push_heap: 在一个已经是堆的序列中尾插一个元素，再调用这个函数，就能重新保持堆的特性
 *      pop_heap: 弹出堆顶，并把它放到序列末尾，通常调用该函数后，应该在pop_back一下，保持堆的大小的正确性
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
using namespace std;

void printVector(const vector<int> &v, const string &name)
{
    cout << name << ':';
    for (int e : v)
        cout << ' ' << e;
    cout << endl;
}

vector<int> getRamdomVector(int begin, int end, int n)
{
    // 指定随机数生成器和分布
    std::default_random_engine generator;
    std::uniform_int_distribution<int> distribution(begin, end); // 生成 beign 到 end 之间的随机数

    // 生成一个大小为 n 的随机序列的 vector
    std::vector<int>randomSequence(n);

    // 使用 std::generate 和 lambda 表达式填充 vector
    std::generate(randomSequence.begin(), randomSequence.end(), [&]()
                  { return distribution(generator); });
    return randomSequence;
}

void testMakeHeap()
{
    // 示例: 将一个序列转换为最大堆
    std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

    // 使用 std::make_heap 转换为最大堆
    std::make_heap(nums.begin(), nums.end());

    std::cout << "大根堆: ";
    for (const auto &num : nums)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    if (std::is_heap(nums.begin(), nums.end()))
    {
        cout << "nums 是大根堆~" << endl;
    }

    // 示例: 将一个序列转换为小根堆
    std::make_heap(nums.begin(), nums.end(), [](int a, int b)
                   { return a > b; });
    std::cout << "小根堆: ";
    for (const auto &num : nums)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    if (std::is_heap(nums.begin(), nums.end(), [](int a, int b)
                     { return a > b; }))
    {
        cout << "nums 是小根堆~" << endl;
    }
}

void testPopHeap()
{
    int myints[] = {10, 20, 30, 5, 15};
    std::vector<int> v(myints, myints + 5);

    std::make_heap(v.begin(), v.end());
    std::cout << "initial max heap   : " << v.front() << '\n';
    printVector(v, "v");

    std::pop_heap(v.begin(), v.end());
    // v.pop_back();
    std::cout << "max heap after pop : " << v.front() << '\n';
    printVector(v, "v");

    v.push_back(99);
    std::push_heap(v.begin(), v.end());
    std::cout << "max heap after push: " << v.front() << '\n';
    printVector(v, "v");

    std::sort_heap(v.begin(), v.end());
    printVector(v, "final v");
}

void testPriorityQueue()
{
    // 创建一个空的向量作为优先队列
    std::vector<int> priorityQueue = {10, 30, 20, 5};

    // 将向量转换为堆结构
    std::make_heap(priorityQueue.begin(), priorityQueue.end());

    printVector(priorityQueue, "PriorityQueue");

    // 在优先队列中插入一个新元素并调整堆结构
    priorityQueue.push_back(25);
    std::push_heap(priorityQueue.begin(), priorityQueue.end());
    printVector(priorityQueue, "PriorityQueue");

    // 从优先队列中弹出堆顶元素
    std::pop_heap(priorityQueue.begin(), priorityQueue.end());
    priorityQueue.pop_back(); // 删除最后一个元素，即堆顶元素
    printVector(priorityQueue, "PriorityQueue");
}

// 题目：给定一个数组，找到数组中第 k 大的元素。
void problem01()
{
    vector<int> v = getRamdomVector(1, 100, 10);
    printVector(v, "v");

    int k = 5;
    // 思路：造一个大根堆，循环k次，每次取出堆顶，然后弹出堆顶
    make_heap(v.begin(), v.end());
    printVector(v, "v");
    vector<int> topK;
    topK.reserve(k);
    while(k--)
    {
        int top = v.front();
        pop_heap(v.begin(), v.end());
        v.pop_back();
        printVector(v, "v");
        
        topK.push_back(top);
    }
    printVector(topK, "前k大的数");
}

int main()
{
    problem01();

    return 0;
}
